1. Field of the Invention
The present invention generally relates to a codebook generating method and, more particularly, to a codebook generating method in use of image compression.
2. Description of the Related Art
In data compression technology, a codebook is usually generated by a codebook generating method when compressing an original image. The codebook has a smaller size than the original image and is thus used to replace the original image for image preservation and transmission. By far, image compression is achieved. On the contrary, during the image decompression, the codebook is decoded by a decoding algorithm to obtain a plurality of reconstructed blocks. The reconstructed blocks are then combined into a reconstructed image. By far, image decompression is achieved.
The conventional codebook generating method usually performs a dividing procedure on an original image to obtain a plurality of original blocks with smaller volume. The original blocks are then converted into a plurality of original vectors by a Vector Quantization mechanism. Finally, a decoding algorithm is used to decode the original vectors to obtain a plurality of code words. The code words have smaller quantity than the original blocks and are representative of the original image. Based on this, the codebook is constructed by the code words.
A conventional decoding algorithm such as a LBG algorithm was proposed by Linda, Buzo and Gray in 1980. The idea of the LBG algorithm is similar to the K-means method known in data clustering methods. In a first step of the LBG algorithm, a value of a distortion index ε, as well as a number K for which the original vectors are to be grouped into, are firstly defined. In a second step of the LBG algorithm, K original vectors are randomly selected from the plurality of original vectors and the K selected original vectors are defined as centroids. In a third step of the LBG algorithm, a Euclidean distance between each original vector and centroid is calculated so that each original vector may be assigned to a corresponding centroid. In a fourth step of the LBG algorithm, a central centroid of the original vectors in each group is determined and the determined central centroid is defined as a new centroid. In a fifth step of the LBG algorithm, a difference between the new and the old centroids in each group, namely, the distortion, is calculated. If the calculated distortion is not smaller than the value of the distortion index ε, the third step is repeated. If the calculated distortion is smaller than the value of the distortion index ε, the whole procedure is terminated. The finally obtained centroids may serve as the code words forming the codebook.
Generally, the aforementioned LBG algorithm is initially performed in a random manner. In addition, the original vectors are in larger number and more complex. Therefore, the obtained result of the LBG algorithm is somewhat unstable.
Another conventional decoding algorithm such as Self-Organizing Map (SOM) is shown in FIG. 1. In a first step of the SOM method, a plurality of pixels of an image is converted into a plurality of input samples 8. In a second step of the SOM method, N neurons 9 are defined and N input samples 8 are randomly selected from the plurality of input samples 8 to be the initial locations of the N neurons 9. In a third step of the SOM method, an input sample 8 is randomly selected from the plurality of input samples 8 in order to calculate a Euclidean distance between the randomly selected input sample 8 and each neuron 9. In a fourth step of the SOM method, the neuron 9 with shortest distance to the randomly selected input sample 8 is defined as a winning neuron 91, with all the neurons 9 located within a circular range centered at the winning neuron 91 with a radius R being defined as neighboring neurons 92. Also in the fourth step of the SOM method, the winning neuron 91 and the neighboring neurons 92 are shifted toward the randomly selected input sample 8 by a distance. In a fifth step of the SOM method, it is determined whether all input samples 8 finish the calculation of Euclidean distance performed in the third step. If not, the procedure goes back to the third step. If so, the whole training procedure is terminated and the radius R is scaled down to initial another round of the training procedure until a predetermined number of times of iteration is satisfied. Thus, a neural network consisting of the N neurons 9 is obtained. Based on this, the N obtained neurons 9 may serve as the codebook in use of image compression.
The above SOMs coding algorithm requires a massive calculations to obtain a desired neural network. In addition, the more the neurons 9 or input samples 8 are, the longer the time is required for calculations. Thus, a lower efficiency is resulted.
Another conventional Fast SOMs coding algorithm improving upon the above SOM method was proposed. The method firstly divides the plurality of input samples 8 into N groups using K-means method, with the number N being equal to the number of the neurons defined in the second step of the above SOM method. Then, locations of the centroids of the N groups are treated as initial locations of the N neurons. Based on this, a preliminary neural network is obtained. In the following processing, the conventional SOM method is used for calculations to reduce the calculation time.
However, the Fast SOMs method is not suitable for processing data in more dimensions as the Fast SOMs method merely processes two dimensional data.
Another conventional hierarchical SOMs (HSOM) coding algorithm was proposed. The main idea of the HSOM method is dividing the calculations of the SOM method into two levels. For example, assume that there are 256 (16×16) neurons defined in the SOM method; in this case, the time complexity is higher. Based on this, the HSOM method firstly performs a first-level training on the input samples using 16 first-level neurons according to the SOM method, and then assigns the plurality of input samples to the 16 first-level neurons in order to obtain 16 groups of input samples. Following, the HSOM method performs a second-level training on all the input samples in each group using 16 second-level neurons according to the SOM method. Based on this, 16 second-level neurons may be obtained from all the input samples in each group. As a result, 256 neurons (16×16) may be obtained, thus reducing the time complexity of the SOM method.
However, since the number of the first-level neurons is the same as that of the second-level neurons in the above HSOM method, the determined result tends to fall in local solution so that the real distribution of the input samples is not easy to obtain. In addition, since each group has different number of input samples but all the groups are trained using the same rather than different number of neurons during the second-level training, the real distribution of the input samples is also not easy to obtain. Thus, a drawback of low efficiency is raised.
Based on the above problems, it is desired to improve the conventional codebook generating method.